1000 1
349426044 544103241 505183817 791548016 372173052 519018454 999206827 593622588 40140726 783470363 15353591 421455099 237369911 428308740 314288867 4651989 26246654 735308180 264107097 76448581 204904962 846780767 242706169 996794780 900883753 211813392 585582486 594098557 720493778 550530789 80336565 498156127 3831628 328582446 675641105 596689679 706621020 613805265 781457434 545719339 409663931 506548937 504540272 729128103 529174422 271674786 465050733 618848332 47821581 719257087 667868825 640492596 471464628 995525909 889577011 255096656 456178452 921471789 105176495 529043682 97721643 270484005 441676082 297685251 726830312 170967024 888895256 743286046 301504944 709021969 594585711 698531955 735615196 152928548 963543929 856983189 978182201 189587286 53629998 817635820 143299718 55372520 989168824 232870452 483915257 453276592 807903733 598572796 772433595 226349719 384144888 674609192 405104999 842252316 530562695 293939312 450410895 390773967 476918175 40754655 229493815 517414359 760473068 245255252 16131160 375276397 92629330 60541956 189467486 917968223 385957735 275445750 591343019 425054606 689056246 565687430 958865170 710911600 549462397 344256482 695065436 602232206 984595375 813414032 145114310 420334599 182610932 66898406 764336257 487390476 578952676 898258577 762961713 853775458 506225104 331692303 333702511 595459811 367671097 98700852 426760263 902378749 624324950 527518121 628621755 614928177 174344083 457164904 399649086 747476629 728060429 41080642 945074233 463689043 704409110 982671705 27210377 32532776 286862519 35240102 93056767 768804325 587890473 546622580 712903647 530500594 28693851 529044963 290083169 117217990 839424624 134252646 417227828 714904944 815820606 54401093 615430646 923661585 103416015 762354972 31337917 511020895 953144547 634897498 58781841 754461476 800267885 217571267 815555567 210598589 784851474 934469103 808471624 536511132 216710829 935155912 387293055 173308359 167010254 774009360 627093871 502787670 753815094 204141529 130649187 574978552 580613212 311604491 336604060 90936431 876153067 920015841 771012559 256603151 864950082 799191660 940985764 578519107 57038322 171141391 476830264 679626249 662137668 625278209 465588124 699181681 826747825 215397070 769710419 806765345 166113895 621914326 646468312 845862100 296981451 6392781 89778198 910867926 436862449 175343929 442517486 749455498 449840934 972198392 766884020 401929700 138905191 499621047 635371698 770864624 575745511 282759803 828492964 802804809 142304141 616867100 92139579 856646818 582113651 922359749 983282330 10163521 778932840 441113974 995462876 718569343 949217903 903062914 742465164 616276553 473937726 684758545 645448747 903176866 854084800 932758687 814783917 635783199 779596180 685087355 457058044 384872809 987562379 208491337 312682612 352770239 457951277 300431745 143453029 934034033 87996213 738181869 694368405 867921254 501737233 411829039 186737851 818345367 316496227 328736313 243843845 751032977 410982274 459035347 829460883 440193015 841023226 330601752 220871673 648018430 951327752 971275001 782590401 975659504 751883806 734412984 797234407 930131626 530074725 572518255 945710171 326623517 576714806 847215495 351442051 25425616 15588256 265284929 279413174 720867420 667289062 43253553 757656770 172490735 707310590 454689981 467302758 490728906 427356434 273569954 484472537 833950915 356441347 828265328 423226433 264277188 170864865 521501193 431541565 279568714 493800308 827771942 847872604 907898854 655090615 106728658 553513380 64561855 40246103 977041644 273307404 306387727 821331768 854757290 693696769 993084322 444115952 692721425 645938917 808972634 197759562 282754174 885399435 723360173 511204805 958564128 755086781 410539813 221077267 474211451 762120374 34070495 532642970 293349094 248852136 814045709 479958262 545713166 799110456 99782260 542410101 576928113 975000573 113145583 995588761 822712548 939223300 14671594 740379290 209937678 366845775 423028199 651978722 129198570 575350097 990389757 538096015 13779273 51769716 606422099 359558644 645652814 467348627 431441322 680514328 570930416 89592448 453508817 110533941 670266491 369321599 498310958 189218106 31898127 113056201 193348412 781887306 321109023 550771211 550966023 354672443 887032820 863496164 815169714 378083096 430484008 47118186 683099377 382946720 263715627 184854694 996058511 375050948 971043778 470018067 907290090 743966252 101293955 205951779 875400050 505564083 844288857 878212794 101411373 85550055 131279878 107680689 456039734 104969354 81194140 731269972 8609593 671419668 115489539 780532196 342216953 776487726 96062071 766216982 587078091 852485432 282307591 411771539 836482584 328729796 897501463 495216246 876926431 225321752 41966047 504110033 994188592 904313264 717494761 568948008 588752562 493874875 213863575 751779060 994904094 933777817 619551642 11751969 498990785 727829347 948355964 40514192 491104766 300989283 884055576 788327318 430895562 35451287 737837340 215502971 829197614 125538611 782747278 453745404 403665097 435331868 995129156 74836426 858073932 108136045 757359466 985329929 850926075 205790454 439115520 730836178 373895475 779734968 711369306 888315313 173170910 903681898 594191518 989954855 664134912 308431095 647141449 581334569 239171118 474817022 862846891 337713055 415596050 619724113 525515110 515511014 490822633 790220662 142582515 563828815 469635844 568003881 132385052 693048733 568945482 816541144 739324035 708012683 661581237 247741477 418108954 313862468 869853393 505057384 253294505 619781353 304384320 156021035 293391436 24222223 693793336 594928044 619157746 684727102 973850115 836976222 938030815 580925299 530369662 405203816 857045546 745754782 22575002 215341348 848157248 415515173 799771103 862461601 694923871 910303584 946347748 635377186 246224924 469743131 645242328 512869277 814730718 691787543 850281980 148019005 278301536 672312968 146832679 238601697 848714803 888836248 548497473 283933594 172450361 457343459 708519368 496087601 266765867 938892793 433420878 599261086 356113429 705401312 667895032 705010834 271508949 232328848 150204929 968393454 298351007 92686708 80855349 142491210 92969595 29005039 237943926 826480751 904901830 432575189 245983291 174100445 577804973 780111086 467941388 441189958 377762485 697737078 990087431 872752401 898455094 825319840 743078494 517948888 754989531 945793550 205162967 212961514 21756451 218381659 814858314 3954122 924043747 132853393 802838055 106910126 761134274 726508467 539075565 246051329 65564092 913217077 982739636 882009313 878959008 402960766 379547812 767288225 56317842 863608685 709974908 431748936 585684873 85204689 928440588 470447889 799109330 956343280 96586171 216786665 400942731 300899073 294833922 67564021 710682153 617980594 980190190 525547273 312252403 323675810 353346466 564814129 382711684 878453736 473606611 342113324 468631117 742243722 660162890 651500268 16317968 88279815 696727142 828144663 7268710 946129102 989385111 183489673 449025594 469875396 107085284 710874576 108953676 522806979 313973094 271443118 52251568 963127061 525011915 184398747 546289484 602534653 422191828 574268737 165760349 899093806 767535831 830819070 130415602 780496978 123991357 538944357 142309744 949322116 298182917 538472637 525749004 968630486 374422847 428154752 376353108 612896716 295226258 163310302 642022055 215563231 468587704 414719800 402071992 45433596 884190972 857934501 357555727 177000450 870825154 390215024 515676808 151981896 317105408 842712215 482051537 918535444 816065981 586891342 883382000 673613348 766861977 764280442 329889212 205039657 188818245 130613047 774113119 722360904 985596934 956705619 453362394 941154711 803536950 728474832 646649729 627458982 545160387 989848422 181956475 780234995 861822639 108373246 493421123 550559604 501533070 642719800 938865962 858837266 640291851 240617702 89050066 56463912 424813155 883437199 489181364 319773704 319244520 771187437 435550619 331758454 778572927 819103855 105387047 701329195 150576418 440297144 152310348 532863059 628134496 850151198 273411280 873466639 442133464 848981292 598419408 478917876 232536001 958090528 641065787 358768011 689510757 340447341 736067413 415388367 487687074 718558778 51149110 797881778 832317800 677976034 79985481 601917080 221701693 805036403 295661006 933819353 569754812 223741487 969725272 443656772 591317777 291235597 866681167 550396823 736890751 768253240 567610990 167617288 201958618 341031055 116188486 961210303 171525389 486103076 475368122 567090521 551665046 229055165 110918273 276839527 339992581 491305814 767267240 163373805 754078337 520332189 733732621 996959971 972186178 819236469 425290213 192489655 838203928 864299124 473369654 353621962 696386787 237656676 663507806 967966958 908241944 384343493 507386506 147309294 64876099 39194442 719235904 980686086 936670079 559903576 227588054 73275751 691556864 938216586 762965496 805991349 553698953 864559151 2282278 895045512 131799286 152423626 631163187 909094126 637917876 530220177 640709831 249836263 279339844 960812528 898370014 833286120 68857532 324802051 840875591 535913561 965918277 523720479 67123238 187347735 487845022 497474377 170214515 815759347 640020119 700954813 97429881 477098544 296829335 164836457 713857367 123304713 323172887 940889711 361066114 536743977 337512485 987482279 501862465 246802481 26025442 897587994 337328432 791746869 896555012 659199112 3553726 447892287 153158229 737630435 878201007 615965899 44405810 813890514 323637658 491551561 104461068 232127791 287262571 700240287 259655403 937857929 801668323 459535524 873511654 856807587 579904787 275172262 852663212 60969459 784481253 268519653 851059710 110129956 777814675 958824470 377115954 646799508 120409646 654840544 885066162 112656343 352502296 753015650 110958459 943392818 907795082 123694763 945488543 137816864 528614671 403992897 147560899 375023825 152666375
692475291 674839201 858283174 696497189 595967143 494000263 326364086 731293426 321458245 25089751 638137165 892396360 599455689 450085253 551472487 238680791 663492221 778961308 156992313 849174947 619985436 461032377 51314089 631820931 589074777 153161358 302761937 767852964 56290902 2732897 778751872 396389637 298956589 905299082 973563320 720785657 601136747 553319416 223556913 208700072 235047824 960045485 525381845 427345549 141108112 232298046 518060098 583251193 813619541 849121620 569867851 85736079 761793594 673717293 669774199 66115270 708587665 696877083 728729217 15979626 551988255 493212932 822550742 459094044 842046107 58979808 125913882 637688525 58086962 960589119 76047267 607774791 688713222 809384384 847737596 432839588 511323818 68449947 35048548 261278677 764022440 431301656 724010061 727191068 789607163 867357718 952548573 756216466 591871893 309251717 614506608 134875810 707542490 689454060 292842516 3405196 803968803 409906148 723782667 980402915 922992445 78650266 369159245 716642575 775505639 32803921 541137155 259065804 133600343 603374558 611485453 868912297 204463542 629401386 445466749 946532746 768779679 845706420 705765658 941671207 512341924 915398924 654044894 560280459 983769801 278944089 377655928 895970965 28548615 351894484 150040011 211787898 232056522 327084619 789023853 677830721 236121460 353212063 50279977 497480261 487599064 599404870 88401790 869319863 476337599 185757130 335781405 511910426 307302759 636686663 81460590 618073541 660479486 846457073 537062668 137741925 376418859 114072716 520534340 922498680 39513222 534438130 452176795 589621970 738474011 240249489 762623813 385192220 686895852 729998826 625401262 317068880 448814188 673013267 941815029 855617343 110762500 968480566 31790700 797864715 389073297 59155216 455516954 377058221 575663076 834702195 681353785 222523504 457106753 304744132 622750648 940858484 387418593 359837309 197308601 832409388 968497264 307166636 469662228 840777952 437730959 971331443 391589075 364935980 553194835 336343942 408256692 593258879 423022532 245789872 782983850 583554461 521090911 786209102 594550620 692510750 303499413 71306706 564067237 99464428 889978698 162133825 201839378 51375049 33343830 551744438 275965543 854476487 9648391 394433245 158436379 237210830 426628509 958091384 344560855 518656025 132843981 74896606 383735290 127197881 871409215 658729335 841461272 652419857 748100624 246698817 753503606 686132824 732136785 357220686 24367248 132593434 782674309 126495044 271111828 303714231 296294439 945755099 23443940 382069987 111530786 844926819 847676056 479364132 27073879 740662843 71673594 956187223 120867099 38977371 623691784 150876716 351559350 600054475 848880629 895920805 403900645 258887721 574674088 834261915 751102808 5162280 948426299 400122937 682961717 485857291 655462781 467653503 820806547 47409198 338145393 887904448 498142208 137824894 327868109 542120996 626730236 376905211 911619196 637356839 985494651 470576701 606698524 688259352 399527527 842276332 792249217 798720923 385688348 567088967 697804336 402318120 991657963 916071070 812825573 744027529 569346455 828377304 812139789 826446944 209800922 815250414 197930829 918318495 679744225 70775662 737452537 276475917 226333644 995802873 579918493 50187720 300834608 615359685 270122360 401062590 12794004 872244763 859681276 836774194 291332599 844720090 830561104 496299070 235411528 930946802 760031438 936226891 457222125 861072618 421935237 600795034 742409021 671069276 533200311 401736382 113925894 255111539 874177372 658221344 272684295 99730035 390375070 967768954 747272311 69709874 948251483 747131485 296541309 513167511 671575719 27899051 468661429 446960418 223943495 878672413 229990321 581590372 460864054 641685950 701634934 603356546 524504868 812118637 132469243 254342838 287992562 875789152 488853421 368816078 42161207 152351388 51446254 622075307 113778110 381983101 360142225 558039492 328497926 298214709 320813408 439681696 441884864 19834693 742049943 902817887 541186901 189195781 78072678 233953586 200517982 419791650 996311410 733947871 719076394 3002394 99622484 182699582 969477691 652058306 169200664 440235966 476839881 748740545 192032704 346110945 850161981 693036818 540671935 423551163 643821495 601866374 576379007 619384695 164103050 425681983 616589019 947690706 159326906 45232439 712900773 307691422 51061125 372903863 926201121 670814017 660125399 449662944 984090504 475240499 982316756 657232421 452285319 427647619 377923410 710386639 199604669 991237203 172819548 897485176 900613696 741185623 344509104 590218640 406762265 513356379 907215426 131611868 70950595 291706810 398460599 383694577 51093168 434574823 882140139 457762493 463048132 382373096 294235243 106563327 447932632 609477589 734063100 637633738 791953720 492425054 19793426 858867718 979538214 167559235 604672090 331545583 232518229 309446105 605147952 376493460 654519406 203140748 77001769 262911065 875148174 341367895 912182411 730684022 204822214 743433037 723892688 413942645 278080666 767542292 914075175 495294135 413411203 858176613 44837107 15437808 323458157 392712078 962822986 148741031 674934585 652544752 362761335 330945975 784013628 381900416 647210616 349225937 52599230 795238218 191959680 736949752 919109757 902498793 597777270 797732611 414087207 243624721 652010613 684778270 200543971 752250374 965612874 609405001 910978761 292068642 747145977 634313944 16545381 293185107 395476537 126843889 380613432 894865306 730065395 528022033 268749367 904264589 185157062 633138567 611803722 608958421 374185606 483524344 790141646 527977393 356051641 78042585 343244820 214534258 686359833 256945400 826863584 509198845 437730068 925915380 66464234 242335052 75089231 544848576 911391840 62321901 510435871 102652452 231288418 865925505 989516814 936693820 980387973 141350974 378737244 318931959 800646993 489915246 960491900 522369689 431732675 974537454 701421458 876893241 959055308 304619696 105690876 84842052 379586767 739381561 709217990 502684664 494692903 921873443 985161524 568810218 586241439 237932700 320030268 131239809 220114424 398898150 760554505 555074424 343775590 369406421 195627385 168531040 738770963 328998228 468743328 274499099 291370651 441425632 547969347 127533410 692532879 795266827 951256414 675874369 105044210 967161083 458418591 783827606 241483455 308392168 610848232 547358869 523501920 194267809 554513361 185141062 271800120 161376776 473368355 555000581 348001819 697105297 212483166 245284354 622063569 270426311 609382708 145298111 153190551 517103816 587830028 581875349 875294109 385287876 176715648 831511087 693606280 546402945 649418975 126731788 166723826 301383898 766310060 793225473 262833381 157256763 471468060 896571061 101825380 677736231 506000028 780087332 953852387 943782067 663026762 219688989 584955850 840235784 669364343 814157252 437040373 761694180 643081259 996669712 963166774 764805913 696497313 984297806 551702482 650040589 498044870 578853276 742650368 509703993 957774526 724885871 120957806 992295594 628441184 979067662 633341883 807366787 298230197 779490324 221357566 664394361 703392380 338858994 671172926 630676821 891568553 28180074 610519799 270729590 20028386 359463445 517283739 243985228 875860481 586085598 87397647 948103646 987118485 552970885 290193194 77425477 987255648 308196126 875936313 418937135 138565082 95351695 957312894 827905885 157560748 431602709 886569900 938883621 141145143 781958335 166967661 666429168 622513675 197327346 883048412 80742077 779135856 988296419 481031435 213323933 978778848 545080352 232189567 105258037 492295562 345165832 958630831 648273983 603588049 770400590 851854984 258451721 987937739 183454074 554481644 6863092 139893187 138104679 460492846 561944310 455367352 455825350 835206551 411079449 95810780 617772442 572715237 64131834 439829 789291707 983668167 851331146 484157567 133209683 186358626 404607313 444053735 764886883 912227535 621130086 775028050 948376383 871843226 829005688 460569460 894928398 390191172 571260040 814840634 591378251 829959363 181578796 625712449 814698055 943979261 528339214 166797660 312304804 491203920 794529131 829308689 250910939 205700877 779751829 327622173 463842487 536725240 405519985 260547308 817736152 373152714 232574970 402046241 895074866 569943215 303182268 551279124 290373259 891093449 208459097 396184399 824838912 51049131 549737736 467040529 90004864 821877982 711665681 500033739 778229839 269972063 11128658 890092453 195963013 512734751 927012285 723316986 308158605 670880898 1597144 297031383 940531878 44339681 689763131 783973504 669463909 17528584 758484758 25764588 53473841 170130360 311188648 766889284 264773574 396183846 830200009 998698856 517142707 60450938 986593633 768226409 452970972 84445521 884460014 867590928 966272760 75590716 852326402 985084502 599094548 615041343 195104195 28494826 48970510 662505554 62554730 641823918 218354714 494947300 118766788 348118330 145854017 623922515 558205876 610179160 761090269 726934900 299948719 969570694 943700767 374993170 41418814 255816567 36841097 631890791 786233472 516662930 244598644 159923364 350325157 653775218 772257676 864368239 42852980 592031588 668135502 980199520 804746438 245671660 899996561 34474627 215279624 460993600 61788154 456617433 819165629 99802059 398415750 200962262 61091322 67068588 981810692 356264420 467771369 602650420 324408216 319901663 929024582 652253548 219719482 735794328 729973733 888779660 549776181 279568210 107046442 397614725 849998248 734913352 702556047 341070457 431293704 830711333 704001570 792954173 737350300 663242890 416215044 909982430 767585536 835235467 483419627 401512985 525373091 747370546 46997408 307529953 721311817 883026939 966794882 24323292 78120841 547638103 948264450 294345703 650608463 893113641 891060261 677999246 408480860 910146635 966205957 427679893 542448577 618730506 10080848 64866674 50385256
